package day_2022_4_to_7.nowcoder;

/**
 * 二叉搜索树的后序遍历序列
 * @author haomin
 * @date 2022/04/20 22:10
 **/
public class VerifySquenceOfBST_20f {
    public boolean VerifySquenceOfBST(int [] sequence) {
        // 序列为空时，直接return false
        if(sequence == null || sequence.length == 0){
            return false;
        }

        return VerifySquenceOfBSTHelper(sequence,0,sequence.length-1);
    }

    private boolean VerifySquenceOfBSTHelper(int[] sequence, int start, int end) {
        // 当子序列首索引大于等于尾索引，说明子序列都是合法后序序列，判断完毕，return true
        if(start >= end){
            return true;
        }
        // 得到当前子序列首索引
        int i = start;
        // 找到子序列中后一段（x的右子树）第一个大于root节点的位置
        while(i < end && sequence[i] < sequence[end]){
            i++;
        }
        // 遍历子序列中后一段（x的右子树）节点
        for (int j = i; j < end; j++) {
            // 当后一段（x的右子树）出现节点小于x时，说明不是合法的后序序列，return false
            if(sequence[j] < sequence[end]){
                return false;
            }
        }
        // 递归判断当前序列的前一段和后一段是否是合法的后序序列
        return VerifySquenceOfBSTHelper(sequence,start,i-1) && VerifySquenceOfBSTHelper(sequence,i,end-1);
    }
}